package Sort2;


public class MergeSort {

	public static void main(String[] args) {
			int[] array={9,7,8,6,5,4,3,2,1};
			mergeSort(array);
			for(int i=0;i<array.length;i++){
				System.out.print(array[i]);
			}
	}
	public static void mergeSort(int[] array){
		if(array==null||array.length==0){
			return;
		}
		mergeSort(array,0,array.length-1);
	}
    public static void mergeSort(int[] array,int low,int high){
    	if(low>=high){
    		return;
    	}
    	int mid = (low+high)/2;
    	mergeSort(array,low,mid);
    	mergeSort(array,mid+1,high);
    	merge(array,low,mid,high);
    }
    public static void merge(int[] array,int low,int mid,int end){
    	int left = low;
    	int right = mid+1;
    	int[] tempArr = new int[end-low+1]; 
    	int third = 0;
    	while(left<=mid&&right<=end){
    		if(array[left]<=array[right]){
    			tempArr[third++] = array[left++];
    		}
    		else{
    			tempArr[third++] = array[right++];
    		}
    	}
    	while(left<=mid){
    		tempArr[third++] = array[left++];
    	}
    	while(right<=end){
    		tempArr[third++] = array[right++];
    	}
    	int i=0;
    	while(low<=end){
    		array[low++] = tempArr[i++];
    		
    	}
    
    }
}
